The editing and display of styled text poses particularly difficult problems in the area of data storage. In particular, the editing of large documents may involve the storage of a significant number of styled characters, i.e., characters which have attributes such as bold, italic, etc. associated with them. The style information for these characters should, ideally, be stored in a manner which allows both fast access to a specific character's style information and rapid modification of that information. Additionally, since style information for each character may include a number of attributes and has the potential to consume a great deal of memory, particular attention must be paid to storage efficiency.
The manner in which style formation is stored is therefore a crucial aspect of any system which operates with characters and character style information. On the one hand, instantaneous access to any stored data item would be highly desirable. On the other, the ability to rapidly revise individual data items is also extremely advantageous. Unfortunately, the goals of rapid random access and quick revisions often operate at cross purposes. For example, array-based storage provides rapid random access to individual stored items. However, adding elements to, or removing elements from, an array can be very time consuming. In the array approach, a block of memory is reserved for the contiguous storage of data elements. Because the elements in the array are stored contiguously, an individual element may be rapidly accessed simply by providing an address having an offset into the array. However, since the array elements generally must be stored contiguously in order to yield this rapid random access, adding elements to or removing elements from the array requires a great deal of time. That is, when an element is removed from the array, other elements in the array must be moved to "fill in the gap" left behind by the removal of the element. Similarly, when an element is added to the array at some location other than the end of the array, existing elements must be moved to make room for the added element. The time-consuming nature of this sort of data element shuffling is particularly egregious in systems involving a large number of data elements, such as a word processing system. Although linked list storage permits the rapid addition or removal of data elements, random access to individual elements can be painfully slow.
Adding data elements to or removing data elements from a linked list is relatively fast and simple. Since each element in the list occupies a separate block of memory and includes a pointer to the next item in the list, an element may be added or deleted simply by adjusting a few pointers. However, a linked list does not provide truly random access to a specific data element, because the list must be searched sequentially, going from element to element via the pointers, until the desired element is encountered.
In short, a system which requires relatively little storage for character style information and which, at the same time, provides rapid random access to stored character style information, would be highly desirable.